package main

import (
	"fmt"
)

// Graph 使用邻接表表示图
type Graph struct {
	vertices map[int][]int
}

// NewGraph 创建一个新的图
func NewGraph() *Graph {
	return &Graph{vertices: make(map[int][]int)}
}

// AddEdge 添加边
func (g *Graph) AddEdge(v, w int) {
	g.vertices[v] = append(g.vertices[v], w)
}

// DFS 深度优先搜索
func (g *Graph) DFS(start int, visited map[int]bool) {
	visited[start] = true
	fmt.Printf("%d ", start)

	for _, neighbor := range g.vertices[start] {
		if !visited[neighbor] {
			g.DFS(neighbor, visited)
		}
	}
}

func main() {
	g := NewGraph()
	g.AddEdge(0, 1)
	g.AddEdge(0, 2)
	g.AddEdge(1, 2)
	g.AddEdge(1, 3)
	g.AddEdge(2, 4)

	visited := make(map[int]bool)
	g.DFS(0, visited)
	fmt.Println()
}
